//回文子串（medium）：https://leetcode.cn/problems/palindromic-substrings/description/
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        int ret = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s[i] == s[j])
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                if (dp[i][j])
                    ret++; // 统计个数
            }
        }
        return ret;
    }
};

//最⻓回⽂⼦串（medium）: https://leetcode.cn/problems/longest-palindromic-substring/description/
class Solution {
public:
    string longestPalindrome(string s) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        int len = 1, begin = 0; // 标记最⻓⼦串的起始位置和⻓度
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s[i] == s[j])
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                if (dp[i][j] && j - i + 1 > len) // 找出⼦串中最⻓的回⽂⼦串
                    len = j - i + 1, begin = i;
            }
        }
        return s.substr(begin, len);
    }
};